#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX_SIZE 1000
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    int Data;
    BinTree Left;
    BinTree Right;
};
BinTree CreatBinTree();
BinTree CreateNode(char v);
// 递归
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
int GetTreeHeight( BinTree BT );
// 非递归
void InorderTraversal_no_recursion( BinTree BT );
void PreorderTraversal_no_recursion( BinTree BT );
void PostorderTraversal_no_recursion( BinTree BT );
void LevelorderTraversal( BinTree BT );
int GetTreeHeight_no_recursion( BinTree BT );

/*
      A
    /    \
    B     C
   / \   / \
   D F   G  I
    /     \
    E      H
*/

/*
Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A
Levelorder: A B C D F G I E H
*/

void main(){
    BinTree BT = CreatBinTree();
    printf("-----recursion-----\n");
    printf("Inorder:");    InorderTraversal(BT);    printf("\n");
    printf("Preorder:");   PreorderTraversal(BT);   printf("\n");
    printf("Postorder:");  PostorderTraversal(BT);  printf("\n");
    printf("-----no recursion-----\n");
    printf("Inorder:");    InorderTraversal_no_recursion(BT);    printf("\n");
    printf("Preorder:");   PreorderTraversal_no_recursion(BT);   printf("\n");
    printf("Postorder:");  PostorderTraversal_no_recursion(BT);  printf("\n");
    printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");
    printf("-----the height of tree-----\n");
    printf("the height of tree: %d\n" ,GetTreeHeight(BT));
    printf("the height of tree: %d\n" ,GetTreeHeight_no_recursion(BT));
}

BinTree CreateNode(char v){
    BinTree ptr = (BinTree)malloc(sizeof(struct TNode));
    ptr->Data = v;
    ptr->Left=ptr->Right=NULL;
    return ptr;
}

BinTree CreatBinTree(){
    BinTree ptr = CreateNode('A');
    ptr->Left = CreateNode('B');
    ptr->Left->Left = CreateNode('D');
    ptr->Left->Right = CreateNode('F');
    ptr->Left->Right->Left = CreateNode('E');
    
    ptr->Right = CreateNode('C');
    ptr->Right->Left = CreateNode('G');
    ptr->Right->Right = CreateNode('I');
    ptr->Right->Left->Right = CreateNode('H');
    return ptr;
}

// TODO: 从中序和先序创建二叉树
BinTree CreateBinTree2(){
    char in_list[9] = {'D','B','E','F','A','G','H','C','I'};
}


// 递归
void InorderTraversal( BinTree BT ){
    if(BT){
        InorderTraversal(BT->Left);
        printf(" %c", BT->Data);
        InorderTraversal(BT->Right);
    }
}
void PreorderTraversal( BinTree BT ){
    if(BT){
        printf(" %c", BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
}
void PostorderTraversal( BinTree BT ){
    if(BT){
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf(" %c", BT->Data);
    }
}
// 非递归
void InorderTraversal_no_recursion( BinTree BT ){
    if(BT){
        // 用数组代替栈
        BinTree stack[MAX_SIZE];
        int top = -1;
        BinTree ptr = BT;
        while(ptr || top > -1){
            if(ptr){
                stack[++top]=ptr;
                ptr=ptr->Left;
            }else{
                ptr = stack[top--];
                printf(" %c", ptr->Data);
                ptr = ptr->Right;
            }
        }
    }
}

void PreorderTraversal_no_recursion( BinTree BT ){
    if(BT){
        // 用数组代替栈
        BinTree stack[MAX_SIZE];
        int top = -1;
        BinTree ptr = BT;
        while(ptr || top > -1){
            if(ptr){
                printf(" %c", ptr->Data);
                stack[++top]=ptr;
                ptr=ptr->Left;
            }else{
                ptr = stack[top--];
                ptr = ptr->Right;
            }
        }
    }
}

void PostorderTraversal_no_recursion( BinTree BT ){
    if(BT){
        // 用数组代替栈
        BinTree stack[MAX_SIZE];
        int top = -1;
        BinTree ptr = BT, r = NULL;
        while(ptr || top > -1){
            if(ptr){
                stack[++top]=ptr;
                ptr=ptr->Left;
            }else{
                ptr = stack[top];
                if(ptr->Right && ptr->Right != r){
                    ptr=ptr->Right;
                }else{
                    top--;
                    printf(" %c", ptr->Data);
                    r = ptr;
                    ptr = NULL;
                }
            }
        }
    }
}

void LevelorderTraversal( BinTree BT ){
    if(BT){
        // 用数组代替队列
        BinTree queue[MAX_SIZE];
        int front=-1,rear=-1;
        queue[++rear]=BT;
        while(front<rear){
            BinTree ptr = queue[++front];
            printf(" %c", ptr->Data);
            if(ptr->Left){
                queue[++rear]=ptr->Left;
            }
            if(ptr->Right){
                queue[++rear]=ptr->Right;
            }
        }
    }
}


int GetTreeHeight( BinTree BT ){
    if(BT){
        int lh = GetTreeHeight(BT->Left);
        int rh = GetTreeHeight(BT->Right);
        if(lh > rh){
            return lh + 1;
        }else{
            return rh + 1;
        }
    }else{
        return 0;
    }
}

int GetTreeHeight_no_recursion( BinTree BT ){
    if(BT){
        BinTree queue[MAX_SIZE];
        int front=-1,rear=-1;
        // last指向一层的最后一个节点，front追上last则高度加一
        int last=0, height=0;
        queue[++rear]=BT;
        while(front<rear){
            BinTree ptr = queue[++front];
            if(ptr->Left){
                queue[++rear]=ptr->Left;
            }
            if(ptr->Right){
                queue[++rear]=ptr->Right;
            }
            if(front==last){
                last = rear;
                height++;
            }
        }
        return height;
    }else{
        return 0;
    }
}